package hot_100;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class 滑动窗口最大值 {
    public static void main(String[] args) {

    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<>();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty()&&deque.peekLast()<=i-k){
                deque.peekLast();
            }
            while(!deque.isEmpty()&&nums[deque.peekFirst()]<=nums[i]){
                deque.pollFirst();
            }
            deque.addFirst(i);
            if(i+1>=k){
                ans.add(nums[deque.peekLast()]);
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
